047 - Monochromatic Diagonal（★7）
キーワードだけチラ見した
$ S[1:i],T[N-i+1:N] を組み合わせたら全ての文字が同じになる。このままだと扱いづらいので、逆転して「$ S[1:i] と組み合わせて全て同じになる文字列は$ T[N-i+1:N] と一致するか？」を解くことにする。
「全て同じになる文字列」は一意に定まり、あとは部分文字列どうしの一致判定を行えばよいがこれはローリングハッシュで可能。
Segment Treeに載せようとするとTLEするが、結局1文字ずつ追加して比較するだけで済むので1文字ずつ更新すれば通る。
こういう形式で出されるとなかなか思い至らない